package day1_array.leetcode.sliding_window;

/**
 * @Author: yuisama
 * @Date: 2022/9/10 17:48
 * @Description:滑动窗口解决至少有k个重复字符子串问题
 * 本题最难的地方在于左窗口滑动的判定
 * 只有当前窗口中出现的字符个数超过限定字符个数，才需要滑动左窗口
 * 因此不断枚举从1到26个字符，寻找最优解
 */
public class Num395_LongestSubString {
    public int longestSubstring(String s, int k) {
        if (s.length() < k) {
            return 0;
        }
        // 结果的字符串长度
        int res = 0;
        // 题目中说了s中只包含小写字母，因此枚举从1到26个字母依次作为窗户中字符的个数
        for (int i = 1; i <= 26 ; i++) {
            int[] window = new int[26];
            int left = 0,right = 0;
            // 窗口中键值对个数，以及有效字符个数(该字符出现次数 >= k)
            int keys = 0,validWindows = 0;
            while (right < s.length()) {
                char c = s.charAt(right);
                right ++;
                if (window[c - 'a'] == 0) {
                    // 第一次出现该字符
                    keys ++;
                }
                // 更新窗口
                window[c - 'a'] ++;
                // 判断当前进入窗口的字符是否为有效字符
                if (window[c - 'a'] == k) {
                    validWindows ++;
                }
                // 当窗口中出现的字符种类超过当前限定的字符数量，滑动左窗口
                while (keys > i) {
                    char d = s.charAt(left);
                    left ++;
                    if (window[d - 'a'] == 1) {
                        // 当前字符就是窗口内最后一次出现的字符
                        keys --;
                    }
                    if (window[d - 'a'] == k) {
                        // 当前字符满足出现次数为k的，有效字符个数 - 1
                        validWindows --;
                    }
                    window[d - 'a'] --;
                }
                // 当且仅当，键值对个数与有效字符个数相等，
                // 说明此时窗口中的字符串为满足题意的子串
                if (keys == validWindows) {
                    res = Math.max(res,right - left);
                }
            }
        }
        return res;
    }
}
